#ifndef FHEAP_H
#define FHEAP_H
#include <memory>
#include <list>
#include <utility>
#include <vector>
using namespace std;

enum TErrorType {
    ET_NoError,
    ET_TooBigPriority,
    ET_RottenHandle,
    ET_HeapIsEmpty
};

template<typename keyType,typename dataType>
class fHeap{
private:
    struct node;
public:
    fHeap(){
        rootList = NULL;
        rootListEnd = rootList;
        min = NULL;
        size = 0;
        maxDegree = 0;
    }

    fHeap (fHeap& other){
        rootList = other.rootList;
        rootListEnd = other.rootListEnd;
        min = other.min;
        size = other.size;
        maxDegree = other.maxDegree;
    }

    class nodeHandle{
    friend class fHeap;
    public:
        nodeHandle(){}
        keyType key(){
            return Node->key;
        }
        dataType data(){
            return Node->data;
        }
        nodeHandle(const nodeHandle& other){
            Node = other.Node;
        }
        ~nodeHandle(){}
    private:
        shared_ptr<node> Node;
        nodeHandle(shared_ptr<node> n){
            Node = n;
        }
    };

    //изменить на хэндл
    nodeHandle insert(keyType k, dataType d){
        node* x = new node(k,d);
        shared_ptr<node> ptr(x);
        if(rootListEnd == NULL){
            rootListEnd = ptr;
        }
        ptr->right = rootList;
        if (rootList != NULL){
            rootList->left = ptr;
        }
        rootList = ptr;
        if (min == NULL || x->key < min->key){
            min = ptr;
        }
        if (x->degree > maxDegree){
            maxDegree = x->degree;
        }
        size++;
        return ptr;
    }

    pair<TErrorType,dataType> minimum(){
        if (min == NULL) return make_pair(ET_HeapIsEmpty,0);
        return make_pair(ET_NoError,min->data);
    }

    void unionHeaps(fHeap& h){
        if (min == NULL || (h.min != NULL && min->key > h.min->key)){
            min = h.min;
        }
        if (h.maxDegree > maxDegree){
            maxDegree = h.maxDegree;
        }
        if (rootList != NULL){
            rootListEnd->right = h.rootList;
        }else{
            rootList = h.rootList;
        }
        if (h.rootList != NULL){
            h.rootList->left = rootListEnd;
        }
        rootListEnd = h.rootListEnd;
        size += h.size;
    }

    pair<TErrorType,dataType> extractMinimum(){
        shared_ptr<node> z = min;
        if (z == NULL) return make_pair(ET_HeapIsEmpty,0);
        for (shared_ptr<node> x = z->child; x != NULL; x = x->right){
            x->parent.reset();
            if (x->right == NULL){
                x->right = rootList;
                rootList->left =x;
                rootList = z->child;
                x->parent.reset();
                break;
            }
        }
        if (z == rootList){
            rootList = z->right;
        }
        if (z == rootListEnd){
            rootListEnd = z->left.lock();
        }
        if (z->left.lock() != NULL ){
            z->left.lock()->right = z->right;
        }
        if (z->right != NULL){
            z->right->left = z->left;
        }
        if (z->right == NULL){
            min = NULL;
        }else{
            min = z->right;
        }
        consolidate();
        size--;
        if (min == NULL) return make_pair(ET_HeapIsEmpty,0);
        return make_pair(ET_NoError,min->data);
    }

    TErrorType decreaseKey(nodeHandle& n,keyType k){
        if (n.Node == NULL){
                return ET_RottenHandle;
        }
        shared_ptr<node> x = n.Node;
        if (k > x->key){
            return  ET_TooBigPriority;
        }
        x->key = k;
        shared_ptr<node> y = x->parent.lock();
        if (y != NULL && x->key < y->key){
            cut(x,y);
            cascadingCut(y);
        }
        if (x->key < min->key){
            min = x;
        }
        return ET_NoError;
    }


    TErrorType deleteNode(nodeHandle& n){
        if(n.Node == NULL){
            return ET_RottenHandle;
        }
        if (rootList == NULL) return ET_HeapIsEmpty;
        decreaseKey(n,min->key-1);
        extractMinimum();
        return ET_NoError;
    }

private:
    shared_ptr<node> rootList;
    shared_ptr<node> rootListEnd;
    shared_ptr<node> min;
    int size;
    int maxDegree;

    struct node {
        keyType key;
        dataType data;
        weak_ptr<node> parent;
        shared_ptr<node> child;
        weak_ptr<node> left;
        shared_ptr<node> right;
        int degree;
        bool mark;

        node(keyType k,dataType d){
            data = d;
            key = k;
            child = NULL;
            right = NULL;
            degree = 0;
            mark = false;
        }
    };

    void consolidate(){
        int d;
        if (rootList == NULL){
            return;
        }
        vector<shared_ptr<node> > A(rootList->degree + 1,NULL);
        for (shared_ptr<node> w = rootList; w != NULL; w = w->right){
            shared_ptr<node> x = w;
            d = x->degree;
            if (d >= A.size()){
                A.resize(2*d);
            }
            while (A[d] != NULL && A[d] != x){
                shared_ptr<node> y = A[d]; //Узел с той же степенью, что и у x
                if (x->key > y->key){
                    swap(x,y);
                    w=x;
                }
                link(y,x);
                A[d] = NULL;
                d++;
                if (d >= A.size()){
                    A.resize(2*d);
                }
            }
            A[d] = x;
        }
        min = NULL;
        for (int i = 0; i  < A.size(); i++){
            if (min == NULL ||(A[i] != NULL  && A[i]->key < min->key)){
                min = A[i];
            }
        }
    }

    void link(shared_ptr<node> y,shared_ptr<node> x){
        if (y == rootList){
            rootList = y->right;
        }
        if (! y->left.expired()){
            shared_ptr<node> ptr(y->left);
            ptr->right = y->right;
        }
        if (y->right != NULL){
            y->right->left = y->left;
        }
 //
        y->left.reset();
        y->right = x->child;
        if(x->child != NULL){
            x->child->left = y;
        }
        x->child = y;
        x->degree++;
        y->parent = x;
        y->mark = false;
    }

    void cascadingCut(shared_ptr<node> y){
        shared_ptr<node> z = y->parent.lock();
        if (z != NULL){
            if (y->mark == false){
                y->mark = true;
            }else{
                cut(y,z);
                cascadingCut(z);
            }
        }
    }

    void cut(shared_ptr<node> x,shared_ptr<node> y){
        y->degree--;
        if(! x->left.expired()){
            shared_ptr<node> ptr(x->left);
            ptr->right = x->right;
        }
        if(x->right != NULL){
            x->right->left = x->left;
        }
        //Удаление x из списка дочерних узлов y, уменьшение degree[y]
        x->right = rootList;
        if (rootList != NULL){
            rootList->left = x;
        }
        rootList = x;
        //Добавление x в список корней H
        x->parent.reset();
        x->mark = false;
    }


};
#endif // FHEAP_H
